package cn.good.yan.sf.t5;

/**
 * 5 判断是否环
 * 龟兔赛跑：
 * 获取：----- 乌龟走一步，兔子走两步，兔子走到终点，不存再环
 * 获取：----- 乌龟走一步，兔子走两步，存在环，乌龟回到起点，然后，兔子和乌龟走一步，他们相遇，这节点就是环的入口
 *
 * @author shengren.yan
 * @create 2024-07-14
 */
public class LoopNode {

    private int value;
    public LoopNode next;

    public LoopNode(int value, LoopNode next) {
        this.value = value;
        this.next = next;
    }

    public boolean isLoop(LoopNode old) {
        LoopNode p1 = old;
        LoopNode p2 = old;
        while (p2 != null && p2.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
            if (p1 == p2) {
                return true;
            }
        }
        return false;
    }

    public int getLoop(LoopNode old) {
        LoopNode p1 = old;
        LoopNode p2 = old;
        while (p2 != null && p2.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
            if (p1 == p2) {
                p1 = old;
                while (true) {
                    if (p1 == p2) {
                        return p1.value;
                    }
                    p1 = p1.next;
                    p2 = p2.next;
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        LoopNode o8 = new LoopNode(8, null);
        LoopNode o7 = new LoopNode(7, o8);
        LoopNode o6 = new LoopNode(6, o7);
        LoopNode o5 = new LoopNode(5, o6);
        LoopNode o4 = new LoopNode(4, o5);
        LoopNode o3 = new LoopNode(3, o4);
        LoopNode o2 = new LoopNode(2, o3);
        LoopNode o1 = new LoopNode(1, o2);

        System.out.println(o1.isLoop(o1));
        o8.next = o5;  // 是 5
        System.out.println(o1.isLoop(o1));
        System.out.println(o1.getLoop(o1));

    }

    public void loop() {
        for (LoopNode i = this; i != null; i = i.next) {
            System.out.println(i.value);
        }
    }

}
